1. Field of the Invention
The present invention relates to an image signal analyzing system for analyzing a shape of an image to be processed or coded on the basis of the shape of the image.
2. Description of the Related Art
As a method of coding image information, there has been a vector quantization method in which a plurality of signals are not quantized separately but divided into blocks of (k.times.l) pixels (k and l being integers not smaller than 1), and each block is regarded as a (k.times.l) dimensional vector, and expressed as a single code.
In this vector quantization method, a vector set (therein after referred to as "codebook") constituted by a plurality of (k.times.l) dimensional representative vectors is prepared, and a representative vector which is closest to an input vector is selected from this codebook by pattern matching between the input vector and the representative vector. The most basic vector quantization is a full search vector quantization for performing pattern matching between an input image block and all of the representative vectors in a codebook. In this case, a full search vector quantization method including a codebook constituted by n representative vectors is required to perform pattern matching n times, resulting in the time for searching the codebook being prolonged if the scale of the codebook is large.
In a effort to solve the foregoing problem, there has been proposed a binary tree search method in Which a codebook is arranged into a tree shape, and pattern matching between an input vector and vectors in each stage is performed stage by stage sequentially from the first stage. According to this measure, the number of times of pattern matching can be made to be log.sub.2 n. However, in the vector quantization searching by use of a binary tree, if judgment at the time of performing the above-mentioned pattern matching is once mistaken, there is a possibility of obtaining a result different from that by the above-mentioned n-times pattern matching. In the vector quantization using a binary tree, therefore, there has been a problem that it is difficult to design a general-purpose codebook, and the performance is often deteriorated.
In order to solve the foregoing problem, various measures of designing a codebook have been proposed.
By way of example, a conventional example of a method of designing a codebook will be described. FIG. 17 shows a flow chart explaining an algorithm in a conventional example to obtain a codebook constituted by representative vectors. Representative samples of an input block (referred to as "training series") are normalized in advance. The normalized samples are defined to be a sample group distributed on a unit super-sphere (a step 161). Next, a principal component as an axis for dividing the normalized samples is obtained (a step 162). By applying a well-known principal component analysis, the above-mentioned sample group on the unit super-sphere is divided into two by use of a super-plane defined with the most contributory vector, that is, a first principal component vector. It is examined which side of the above-mentioned principal component respective vectors of the samples on the unit super-sphere belong to (a step 163). Next, the center of gravity of the respective vectors of the samples is obtained in each of divisional spaces (a step 164). In addition, it is decided in advance that the number of divisional spaces is 2.sup.r, and the number of time of repeating the operation of division is n, and 1 is added to n whenever this operation of division has been performed once (a step 165). Next, it is examined whether n has reached 2.sup.r or not. If n has not reached 2.sup.r, the operation of dividing a space is repeated n times (a step 166 ). As a result of the repetition 2.sup.r times of the above-mentioned operation of division, representative vectors are obtained (a step 167). A binary tree codebook is designed in this manner. The details of the algorithm shown in the above-mentioned flowchart has been disclosed in Watanabe et al., "Method of Designing a Binary Tree Search CodeBook", Papers of Institute of Electronics, Information and Communication Engineers of Japan.
FIG. 16 is a block diagram illustrating a shape analysis unit using a codebook designed according to a conventional method. In FIG. 16, a shape analysis unit 20 includes a codebook memory 21 for storing representative vectors, an output switch unit 22 for supplying a representative vector read from the codebook memory 21 to an inner product computing unit in a predetermined stage, first and second inner product computing units 23 and 24 for computing inner products between representative vectors and a mean separated block, a comparator 25 for comparing the respective sizes of the results computed by the first and second inner product computing portions 23 and 24, an index latch 26 for holding a sign expressing the size compared by the comparator 25, and a representative vector selection unit 27 for generating an address for selecting a representative vector stored in the codebook memory 21 on the basis of the sign held by the index latch 26, and giving an instruction of switch to the output switch unit 22.
The first inner product computing unit 23 computes an inner product between a mean separated block in which a mean of an input block extracted from an input image is separated, and a representative vector Y.sub.1 obtained in advance by the procedure of FIG. 17 and stored in the codebook memory 21. In the same manner, the second inner product computing unit 24 computes an inner product between the mean separated block and a representative vector Y.sub.2 obtained in advance by the procedure of FIG. 17 and stored in the codebook memory 21.
After that, the results of the inner products computed by the respective inner product computing units 23 and 24 are compared with each other by the comparator 25. The respective sizes of the representative vectors Y.sub.1 and Y.sub.2 are judged by the output of the comparator 25. A positive or negative sign obtained thus is held by the index latch 26 sequentially, for example, as "1" or "0", and is used for computing inner products in the next stage. That is, the representative vector selection unit 27 reads the sign of the index latch 26, and assigns the address of representative vectors stored in the codebook memory 21 as well as the inner product computing units 23 and 24 corresponding to a predetermined stage in the output switch unit 22 on the basis of this read sign.
Next, representative vectors stored in the codebook memory 21 the address which have been assigned by the representative vector selection unit 27 are read, and at the same time the output switch unit 22 is switched to supply the representative vectors to the inner product computing units 23 and 24 in the stage assigned by the representative vector selection unit 27. The respective sizes of inner products are compared with each other in the same manner as mentioned above, and an index thereof is held by the index latch 26. In the same manner, such an operation is repeated up to the n-th stage set in the codebook, so that the results of coding of the input block can be obtained in the index latch 26.
By the way, a codebook designed by a method as shown in FIG. 17 expresses only waveform (shape) information normalized into mean 0 and dispersion 1, which is called "Shape". It is therefore necessary to obtain the mean and dispersion of an input block other than "Shape" when vector quantization is performed. On the other hand, since the codebook has the mean 0 and the dispersion 1, pattern matching can be realized by a maximum inner product regulation in which inner product values between the input block and the codebook constituted by representative vectors are obtained, and a representative vector making its inner product value large is selected as a high-approximate representative vector.
In addition, an approximate value of dispersion is obtained from the inner product value, called "Gain". The larger the difference between the codebook constituted by representative vectors and the input vectors is, i.e., the larger mismatching is, the smaller the "Gain" is. Thus, the use of the "Gain" makes it possible to perform a pattern matching operation and attenuate the distortion of quantization by a single operation. This method has been called "Gain"/"Shape" VQ, and reported in the paper by Buzo et al., entitled "Speech coding based upon vector quantization", and described in IEEE Trans. on Acoust.
However, such a method of designing a codebook as shown in FIG. 17 is a method for general binary tree search quantization, so that the following problems have been produced in the case of performing "Shape" analysis by use of a codebook designed by this method.
(1) Representative vectors obtained by repeating the operation of dividing a signal space into two along a super-plane test algorithm by use of a conventional system are obtained newly, while centers of gravity in respective stages are obtained, so that the representative vectors are not on a super-sphere. That is, quantized representative vectors obtained in the last stage are not normalized with respective to Gain. It is therefore necessary to normalize the representative vectors with respective to "Gain" newly after the operation of dividing spaces is finished, so that procedures for designing a codebook are made complicated. PA0 (2) The new representative vectors obtained while centers of gravity in respective stages are obtained as above mentioned, are not ideal "for pixel values to increase or decrease monotonously in a certain predetermined direction". Therefore, the vectors cannot always "express Shape of a block". For example, there is a case where representative vectors are such that it is difficult to read the increase/decrease of pixel values. This results in a block having no meanings on shape. PA0 (3) Since a codebook designed by use of a conventional system must store in it all of representative vectors divided by a super-plane, the quantity of a memory for the codebook becomes large, so that there has been a problem on the economy of realized memory scale and so on for using the code book for "Shape" analysis.
It is difficult to use such representative vectors for "Shape" analysis.